// https://leetcode.cn/problems/longest-turbulent-subarray/

// 题干：给定一个整数数组 arr ，返回 arr 的 最大湍流子数组的长度 。
//      如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是 湍流子数组 。
//      更正式地来说，当 arr 的子数组 A[i], A[i+1], ..., A[j] 满足仅满足下列条件时，我们称其为湍流子数组：
//      若 i <= k < j ：
//      当 k 为奇数时， A[k] > A[k+1]，且
//      当 k 为偶数时，A[k] < A[k+1]；
//      或 若 i <= k < j ：
//      当 k 为偶数时，A[k] > A[k+1] ，且
//      当 k 为奇数时， A[k] < A[k+1]。

// 示例：输入：arr = [9,4,2,10,7,8,8,1,9]
//      输出：5

// 碎语：

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int maxTurbulenceSize(vector<int>& arr)
    {
        // 以i位置元素为结尾的所有子数组中，最长的湍流子数组的长度
        // 不能解决问题，所以需要换一个状态表示
        // 因为当位于i位置的时候，发现一个状态表示不能解决问题

        // f[i]表示以i位置元素为结尾的所有子数组中，最后呈现“上升”状态下最长的湍流子数组长度
        // g[i]表示以i位置元素为结尾的所有子数组中，最后呈现“下降”状态下最长的湍流子数组长度

        int ret = 0;
        int n = arr.size(); if (n == 1) return 1;
        vector<int> f(n, 1), g(n, 1);

        for (int i = 1 ; i < n ; i++){
            int a = arr[i], b = arr[i - 1];

            if (a > b) f[i] = g[i - 1] + 1;
            else if (a < b) g[i] = f[i - 1] + 1;

            ret = max(ret, max(g[i], f[i]));
        }

        return ret;
    }
};

int main()
{
    Solution sol;
    vector<int> arr = {9,4,2,10,7,8,8,1,9};

    cout << sol.maxTurbulenceSize(arr) << endl;

    return 0;
}